Although we now have a method for "solving" RL problems, we need to mention the hidden attached strings.

• We required perfect information about our system
• Our method is extremely computationally intensive

Now, we shall focus on improving these processes.

First, we relax the assumption that we need to know \(q(s', r | s, a)\). For example, in the Gambler's game, now the weighting of the coin is unknown.

We have two options

• We may try and estimate the probabilities of each transition (model based)
• We may go straight towards estimating the value function of actions (model free)

In this section, we explore the latter.

To estimate the \(v_\pi(s, a)\), we must first take trajectories.

\[ (s_0, a_0)^m \xrightarrow{r^m_0} (s_1, a_1)^m \xrightarrow{r^m_1} \ldots \xrightarrow{r^m_{T-1}} (s_T, a_T)^{m} \]

Note that now we have joined together \(s^m_{i, \mathrm{new}} := (s_i, a_i)^m\), the \(i\)-th state in the \(m\)-th trajectory.

Now, we have that the value of a state is the average reward across the trajectories, or that

\[ v_\pi(s) \approx \frac{1}{C(s)} \sum_{m=1}^M \sum_{t=0}^{T_m - 1} \mathbb{I}[s^m_t = s] g^m_t \]

where \(C(s)\) is the total count of visits to \(s\) in all \(M\) trajectories.

As a further approximation, we may designate \(\alpha \approx C(s)\), the learning rate. This allows us to update \(v_\pi(s)\) incrementally, after each trajectory.

\[ V(s_t) \xleftarrow{} V(s_t) + \alpha(g^{(m)}_t - V(s_t)) \]

Thus, after obtaining our value function, we may take the simple policy \(\pi'(s) = \mathrm{argmax_a} v_\pi(s, a)\)

Suppose we had a bad initial policy (very reasonable) that did not explore every state. Then, if this unexplored state was part of the optimal strategy, then we would never be optimal.

In general, we have two conflicting ideas

• Exploitation: Maximizing returns means choosing the best path
• Exploration: Optimal policies require visiting all paths

Thus, we describe the simplest \(\epsilon\)-greedy policy, where with probability epsilon, we take a random action, and otherwise we take the highest return action.

Finally, we further generalize \(\alpha\)-Monte Carlo. In particular, we allow for the data collection policy \(b\) to differ from our decision policy \(pi\), applying importance sampling.

Skipping the derivation, the only modification to the algorithm is to discount the reward \(g_t\) by a correlation coefficient \(\rho(b, \pi)\)

\[ g^{(m)}_t = \rho^m_t(b, \pi)(r^{(m)}_{t+1} + \gamma r^{(m)}_{t+2} + \ldots) \]

where

\[ \rho^{(m)}_t(b, \pi) = \prod_{\tau = t + 1}^{T_m} \frac{\pi(a^{(m)}_\tau | s^{(m)}_\tau)}{b(a^{(m)}_\tau | s^{(m)}_\tau)} \]

This allows us to change \(b\) independently of \(\pi\), for example by doing parallel trajectories all under different \(b\) policies.

An implementation of an RL algorithm to solve blackjack is here.

Home 1 2 3 4(b) 5 6 Next